The Arsenal Files 1/The Arsenal Files (Arsenal Computer).ISO/archive/unixarc.pt4

Internet Message Format | 1994-01-23 | 68.1 KB

From pacbell!ames!mailrus!cornell!rochester!bbn!bbn.com!rsalz Fri Jul  1 13:12:42 1988
From: [e-mail] (Rich Salz)
Newsgroups: comp.sources.unix
Subject: v15i080:  ARC (PC compression program), v5.21, Part04/05
Message-ID: <[e-mail]>
Date: 1 Jul 88 20:12:42 GMT

Submitted-by: [e-mail]
Posting-number: Volume 15, Issue 80
Archive-name: arc5.21/part04

#--------------------------------CUT HERE-------------------------------------
#! /bin/sh
#
# This is a shell archive.  Save this into a file, edit it
# and delete all lines above this comment.  Then give this
# file to sh by executing the command "sh file".  The files
# will be extracted into the current directory owned by
# you with default permissions.
#
# The files contained herein are:
#
# -rw-r--r--  1 hyc         22109 Jun  1 20:01 arclzw.c
# -rw-r--r--  1 hyc          3026 Jun  1 19:41 arcmatch.c
# -rw-r--r--  1 hyc          8418 Jun 13 14:17 arcmisc.c
# -rw-r--r--  1 hyc          7376 Jun  2 16:27 arcpack.c
# -rw-r--r--  1 hyc          3838 Jun  1 19:57 arcrun.c
# -rw-r--r--  1 hyc          1645 Apr 17 18:53 arcs.h
# -rw-------  1 hyc         14613 Jun  2 16:27 arcsq.c
#
echo 'x - arclzw.c'
if test -f arclzw.c; then echo 'shar: not overwriting arclzw.c'; else
sed 's/^X//' << '________This_Is_The_END________' > arclzw.c
X/*
X * $Header: arclzw.c,v 1.4 88/06/01 16:27:59 hyc Locked $
X */
X
X/*
X * ARC - Archive utility - ARCLZW
X *
X * Version 2.03, created on 10/24/86 at 11:46:22
X *
X * (C) COPYRIGHT 1985,86 by System Enhancement Associates; ALL RIGHTS RESERVED
X *
X * By:  Thom Henderson
X *
X * Description: This file contains the routines used to implement Lempel-Zev
X * data compression, which calls for building a coding table on the fly.
X * This form of compression is especially good for encoding files which
X * contain repeated strings, and can often give dramatic improvements over
X * traditional Huffman SQueezing.
X *
X * Language: Computer Innovations Optimizing C86
X *
X * Programming notes: In this section I am drawing heavily on the COMPRESS
X * program from UNIX.  The basic method is taken from "A Technique for High
X * Performance Data Compression", Terry A. Welch, IEEE Computer Vol 17, No 6
X * (June 1984), pp 8-19.  Also see "Knuth's Fundamental Algorithms", Donald
X * Knuth, Vol 3, Section 6.4.
X *
X * As best as I can tell, this method works by tracing down a hash table of code
X * strings where each entry has the property:
X *
X * if <string> <char> is in the table then <string> is in the table.
X */
X#include <stdio.h>
X#include "arc.h"
X
Xvoid    putc_pak(), abort(), putc_ncr();
Xint    getc_unp();
X#if    MSDOS
Xchar    *setmem();
X#else
Xchar    *memset();
X#endif
X
Xstatic void    putcode();
X/* definitions for older style crunching */
X
X#define FALSE    0
X#define TRUE     !FALSE
X#define TABSIZE  4096
X#define NO_PRED  0xFFFF
X#define EMPTY    0xFFFF
X#define NOT_FND  0xFFFF
X
Xstatic unsigned short inbuf;    /* partial input code storage */
Xstatic int      sp;        /* current stack pointer */
X
Xstruct entry {        /* string table entry format */
X    char            used;    /* true when this entry is in use */
X    unsigned char   follower;    /* char following string */
X    unsigned short  next;    /* ptr to next in collision list */
X    unsigned short  predecessor;    /* code for preceeding string */
X};            /* string_tab[TABSIZE];    /* the code string table */
X
X
X/* definitions for the new dynamic Lempel-Zev crunching */
X
X#define BITS   12        /* maximum bits per code */
X#define HSIZE  5003        /* 80% occupancy */
X#define INIT_BITS 9        /* initial number of bits/code */
X
Xstatic int      n_bits;        /* number of bits/code */
Xstatic int      maxcode;    /* maximum code, given n_bits */
X#define MAXCODE(n)      ((1<<(n)) - 1)    /* maximum code calculation */
Xstatic int      maxcodemax = 1 << BITS;    /* largest possible code (+1) */
X
Xstatic char     buf[BITS];    /* input/output buffer */
X
Xstatic unsigned char lmask[9] =    /* left side masks */
X{
X 0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00
X};
Xstatic unsigned char rmask[9] =    /* right side masks */
X{
X 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff
X};
X
Xstatic int      offset;        /* byte offset for code output */
Xstatic long     in_count;    /* length of input */
Xstatic long     bytes_out;    /* length of compressed output */
Xstatic long     bytes_ref;    /* output quality reference */
Xstatic long     bytes_last;    /* output size at last checkpoint */
Xstatic unsigned short ent;
X
X/*
X * To save much memory (which we badly need at this point), we overlay the
X * table used by the previous version of Lempel-Zev with those used by the
X * new version.  Since no two of these routines will be used together, we can
X * safely do this.
X */
X
Xextern long     htab[HSIZE];        /* hash code table   (crunch) */
Xextern unsigned short codetab[HSIZE];    /* string code table (crunch) */
Xstatic struct    entry *string_tab=(struct entry *)htab;    /* old crunch string table */
X
Xstatic unsigned short *prefix=codetab;    /* prefix code table (uncrunch) */
Xstatic unsigned char *suffix=(unsigned char *)htab;    /* suffix table (uncrunch) */
X
Xstatic int      free_ent;    /* first unused entry */
Xstatic int      firstcmp;    /* true at start of compression */
Xextern unsigned char stack[HSIZE];    /* local push/pop stack */
X
X/*
X * block compression parameters -- after all codes are used up, and
X * compression rate changes, start over.
X */
X
Xstatic int      clear_flg;
X#define CHECK_GAP 2048        /* ratio check interval */
Xstatic long     checkpoint;
Xvoid            upd_tab();
X
X/*
X * the next two codes should not be changed lightly, as they must not lie
X * within the contiguous general code space.
X */
X#define FIRST   257        /* first free entry */
X#define CLEAR   256        /* table clear output code */
X
X/*
X * The cl_block() routine is called at each checkpoint to determine if
X * compression would likely improve by resetting the code table.  The method
X * chosen to determine this is based on empirical observation that, in
X * general, every 2k of input data should compress at least as well as the
X * first 2k of input.
X */
X
Xstatic          void
Xcl_block(t)            /* table clear for block compress */
X    FILE           *t;    /* our output file */
X{
X    checkpoint = in_count + CHECK_GAP;
X
X    if (bytes_ref) {
X        if (bytes_out - bytes_last > bytes_ref) {
X            setmem(htab, HSIZE * sizeof(long), 0xff);
X            free_ent = FIRST;
X            clear_flg = 1;
X            putcode(CLEAR, t);
X            bytes_ref = 0;
X        }
X    } else
X        bytes_ref = bytes_out - bytes_last;
X
X    bytes_last = bytes_out;    /* remember where we were */
X}
X
X/*****************************************************************
X *
X * Output a given code.
X * Inputs:
X *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
X *              that n_bits =< (LONG)wordsize - 1.
X * Outputs:
X *      Outputs code to the file.
X * Assumptions:
X *      Chars are 8 bits long.
X * Algorithm:
X *      Maintain a BITS character long buffer (so that 8 codes will
X * fit in it exactly).  When the buffer fills up empty it and start over.
X */
X
Xstatic          void
Xputcode(code, t)        /* output a code */
X    int             code;    /* code to output */
X    FILE           *t;    /* where to put it */
X{
X    int             r_off = offset;    /* right offset */
X    int             bits = n_bits;    /* bits to go */
X    char           *bp = buf;    /* buffer pointer */
X    int             n;    /* index */
X
X    register int    ztmp;
X
X    if (code >= 0) {    /* if a real code *//* Get to the first byte. */
X        bp += (r_off >> 3);
X        r_off &= 7;
X
X        /*
X         * Since code is always >= 8 bits, only need to mask the
X         * first hunk on the left.
X         */
X        ztmp = (code << r_off) & lmask[r_off];
X        *bp = (*bp & rmask[r_off]) | ztmp;
X        bp++;
X        bits -= (8 - r_off);
X        code >>= (8 - r_off);
X
X        /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
X        if (bits >= 8) {
X            *bp++ = code;
X            code >>= 8;
X            bits -= 8;
X        }
X        /* Last bits. */
X        if (bits)
X            *bp = code;
X        offset += n_bits;
X
X        if (offset == (n_bits << 3)) {
X            bp = buf;
X            bits = n_bits;
X            bytes_out += bits;
X            do
X                putc_pak(*bp++, t);
X            while (--bits);
X            offset = 0;
X        }
X        /*
X         * If the next entry is going to be too big for the code
X         * size, then increase it, if possible.
X         */
X        if (free_ent > maxcode || clear_flg > 0) {
X            /*
X             * Write the whole buffer, because the input side
X             * won't discover the size increase until after
X             * it has read it.
X             */
X            if (offset > 0) {
X                bp = buf;    /* reset pointer for writing */
X                bytes_out += n = n_bits;
X                while (n--)
X                    putc_pak(*bp++, t);
X            }
X            offset = 0;
X
X            if (clear_flg) {    /* reset if clearing */
X                maxcode = MAXCODE(n_bits = INIT_BITS);
X                clear_flg = 0;
X            } else {/* else use more bits */
X                n_bits++;
X                if (n_bits == BITS)
X                    maxcode = maxcodemax;
X                else
X                    maxcode = MAXCODE(n_bits);
X            }
X        }
X    } else {        /* dump the buffer on EOF */
X        bytes_out += n = (offset + 7) / 8;
X
X        if (offset > 0)
X            while (n--)
X                putc_pak(*bp++, t);
X        offset = 0;
X    }
X}
X
X/*****************************************************************
X *
X * Read one code from the standard input.  If EOF, return -1.
X * Inputs:
X *      cmpin
X * Outputs:
X *      code or -1 is returned.
X */
X
Xstatic          int
Xgetcode(f)            /* get a code */
X    FILE           *f;    /* file to get from */
X{
X    int             code;
X    static int      offset = 0, size = 0;
X    int             r_off, bits;
X    unsigned char  *bp = (unsigned char *) buf;
X
X    if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
X        /*
X         * If the next entry will be too big for the current code
X         * size, then we must increase the size. This implies
X         * reading a new buffer full, too.
X         */
X        if (free_ent > maxcode) {
X            n_bits++;
X            if (n_bits == BITS)
X                maxcode = maxcodemax;    /* won't get any bigger
X                             * now */
X            else
X                maxcode = MAXCODE(n_bits);
X        }
X        if (clear_flg > 0) {
X            maxcode = MAXCODE(n_bits = INIT_BITS);
X            clear_flg = 0;
X        }
X        for (size = 0; size < n_bits; size++) {
X            if ((code = getc_unp(f)) == EOF)
X                break;
X            else
X                buf[size] = (char) code;
X        }
X        if (size <= 0)
X            return -1;    /* end of file */
X
X        offset = 0;
X        /* Round size down to integral number of codes */
X        size = (size << 3) - (n_bits - 1);
X    }
X    r_off = offset;
X    bits = n_bits;
X
X    /*
X     * Get to the first byte.
X     */
X    bp += (r_off >> 3);
X    r_off &= 7;
X
X    /* Get first part (low order bits) */
X    code = (*bp++ >> r_off);
X    bits -= 8 - r_off;
X    r_off = 8 - r_off;    /* now, offset into code word */
X
X    /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
X    if (bits >= 8) {
X        code |= *bp++ << r_off;
X        r_off += 8;
X        bits -= 8;
X    }
X    /* high order bits. */
X    code |= (*bp & rmask[bits]) << r_off;
X    offset += n_bits;
X
X    return code & MAXCODE(BITS);
X}
X
X/*
X * compress a file
X *
X * Algorithm:  use open addressing double hashing (no chaining) on the prefix
X * code / next character combination.  We do a variant of Knuth's algorithm D
X * (vol. 3, sec. 6.4) along with G. Knott's relatively-prime secondary probe.
X * Here, the modular division first probe is gives way to a faster
X * exclusive-or manipulation.  Also do block compression with an adaptive
X * reset, where the code table is cleared when the compression ratio
X * decreases, but after the table fills.  The variable-length output codes
X * are re-sized at this point, and a special CLEAR code is generated for the
X * decompressor.
X */
X
Xvoid
Xinit_cm(t)            /* initialize for compression */
X    FILE           *t;    /* where compressed file goes */
X{
X    offset = 0;
X    bytes_out = bytes_last = 1;
X    bytes_ref = 0;
X    clear_flg = 0;
X    in_count = 1;
X    checkpoint = CHECK_GAP;
X    maxcode = MAXCODE(n_bits = INIT_BITS);
X    free_ent = FIRST;
X    setmem(htab, HSIZE * sizeof(long), 0xff);
X    n_bits = INIT_BITS;    /* set starting code size */
X
X    putc_pak(BITS, t);    /* note our max code length */
X
X    firstcmp = 1;        /* next byte will be first */
X}
X
Xvoid
Xputc_cm(c, t)            /* compress a character */
X    unsigned char   c;    /* character to compress */
X    FILE           *t;    /* where to put it */
X{
X    static long     fcode;
X    static int      hshift;
X    int             i;
X    int             disp;
X
X    if (firstcmp) {        /* special case for first byte */
X        ent = c;    /* remember first byte */
X
X        hshift = 0;
X        for (fcode = (long) HSIZE; fcode < 65536L; fcode *= 2L)
X            hshift++;
X        hshift = 8 - hshift;    /* set hash code range bound */
X
X        firstcmp = 0;    /* no longer first */
X        return;
X    }
X    in_count++;
X
X    fcode = (long) (((long) c << BITS) + ent);
X    i = (c << hshift) ^ ent;/* xor hashing */
X
X    if (htab[i] == fcode) {
X        ent = codetab[i];
X        return;
X    } else if (htab[i] < 0)    /* empty slot */
X        goto nomatch;
X    disp = HSIZE - i;    /* secondary hash (after G.Knott) */
X    if (i == 0)
X        disp = 1;
X
Xprobe:
X    if ((i -= disp) < 0)
X        i += HSIZE;
X
X    if (htab[i] == fcode) {
X        ent = codetab[i];
X        return;
X    }
X    if (htab[i] > 0)
X        goto probe;
X
Xnomatch:
X    putcode(ent, t);
X    ent = c;
X    if (free_ent < maxcodemax) {
X        codetab[i] = free_ent++;    /* code -> hashtable */
X        htab[i] = fcode;
X    }
X    if (in_count >= checkpoint)
X        cl_block(t);    /* check for adaptive reset */
X}
X
Xlong
Xpred_cm(t)            /* finish compressing a file */
X    FILE           *t;    /* where to put it */
X{
X    putcode(ent, t);    /* put out the final code */
X    putcode(-1, t);        /* tell output we are done */
X
X    return bytes_out;    /* say how big it got */
X}
X
X/*
X * Decompress a file.  This routine adapts to the codes in the file building
X * the string table on-the-fly; requiring no table to be stored in the
X * compressed file.  The tables used herein are shared with those of the
X * compress() routine.  See the definitions above.
X */
X
Xvoid
Xdecomp(f, t)            /* decompress a file */
X    FILE           *f;    /* file to read codes from */
X    FILE           *t;    /* file to write text to */
X{
X    unsigned char  *stackp;
X    int             finchar;
X    int             code, oldcode, incode;
X
X    if ((code = getc_unp(f)) != BITS)
X        abort("File packed with %d bits, I can only handle %d", code, BITS);
X
X    n_bits = INIT_BITS;    /* set starting code size */
X    clear_flg = 0;
X
X    /*
X     * As above, initialize the first 256 entries in the table.
X     */
X    maxcode = MAXCODE(n_bits = INIT_BITS);
X    setmem(prefix, 256 * sizeof(short), 0);    /* reset decode string table */
X    for (code = 255; code >= 0; code--)
X        suffix[code] = (unsigned char) code;
X
X    free_ent = FIRST;
X
X    finchar = oldcode = getcode(f);
X    if (oldcode == -1)    /* EOF already? */
X        return;        /* Get out of here */
X    putc_ncr((unsigned char) finchar, t);    /* first code must be 8 bits=char */
X    stackp = stack;
X
X    while ((code = getcode(f)) > -1) {
X        if (code == CLEAR) {    /* reset string table */
X            setmem(prefix, 256 * sizeof(short), 0);
X            clear_flg = 1;
X            free_ent = FIRST - 1;
X            if ((code = getcode(f)) == -1)    /* O, untimely death! */
X                break;
X        }
X        incode = code;
X        /*
X         * Special case for KwKwK string.
X         */
X        if (code >= free_ent) {
X            if (code > free_ent) {
X                if (warn) {
X                    printf("Corrupted compressed file.\n");
X                    printf("Invalid code %d when max is %d.\n",
X                        code, free_ent);
X                }
X                nerrs++;
X                return;
X            }
X            *stackp++ = finchar;
X            code = oldcode;
X        }
X        /*
X         * Generate output characters in reverse order
X         */
X        while (code >= 256) {
X            *stackp++ = suffix[code];
X            code = prefix[code];
X        }
X        *stackp++ = finchar = suffix[code];
X
X        /*
X         * And put them out in forward order
X         */
X        do
X            putc_ncr(*--stackp, t);
X        while (stackp > stack);
X
X        /*
X         * Generate the new entry.
X         */
X        if ((code = free_ent) < maxcodemax) {
X            prefix[code] = (unsigned short) oldcode;
X            suffix[code] = finchar;
X            free_ent = code + 1;
X        }
X        /*
X         * Remember previous code.
X         */
X        oldcode = incode;
X    }
X}
X
X
X/*************************************************************************
X * Please note how much trouble it can be to maintain upwards            *
X * compatibility.  All that follows is for the sole purpose of unpacking *
X * files which were packed using an older method.                        *
X *************************************************************************/
X
X
X/*
X * The h() pointer points to the routine to use for calculating a hash value.
X * It is set in the init routines to point to either of oldh() or newh().
X *
X * oldh() calculates a hash value by taking the middle twelve bits of the square
X * of the key.
X *
X * newh() works somewhat differently, and was tried because it makes ARC about
X * 23% faster.  This approach was abandoned because dynamic Lempel-Zev
X * (above) works as well, and packs smaller also.  However, inadvertent
X * release of a developmental copy forces us to leave this in.
X */
X
Xstatic unsigned short(*h) ();    /* pointer to hash function */
X
Xstatic unsigned short
Xoldh(pred, foll)        /* old hash function */
X    unsigned short  pred;    /* code for preceeding string */
X    unsigned char   foll;    /* value of following char */
X{
X    long            local;    /* local hash value */
X
X    local = ((pred + foll) | 0x0800) & 0xFFFF; /* create the hash key */
X    local *= local;        /* square it */
X    return (local >> 6) & 0x0FFF;    /* return the middle 12 bits */
X}
X
Xstatic unsigned short
Xnewh(pred, foll)        /* new hash function */
X    unsigned short  pred;    /* code for preceeding string */
X    unsigned char   foll;    /* value of following char */
X{
X    return (((pred + foll) & 0xFFFF) * 15073) & 0xFFF; /* faster hash */
X}
X
X/*
X * The eolist() function is used to trace down a list of entries with
X * duplicate keys until the last duplicate is found.
X */
X
Xstatic unsigned short
Xeolist(index)            /* find last duplicate */
X    unsigned short  index;
X{
X    int             temp;
X
X    while (temp = string_tab[index].next)    /* while more duplicates */
X        index = temp;
X
X    return index;
X}
X
X/*
X * The hash() routine is used to find a spot in the hash table for a new
X * entry.  It performs a "hash and linear probe" lookup, using h() to
X * calculate the starting hash value and eolist() to perform the linear
X * probe.  This routine DOES NOT detect a table full condition.  That MUST be
X * checked for elsewhere.
X */
X
Xstatic unsigned short
Xhash(pred, foll)        /* find spot in the string table */
X    unsigned short  pred;    /* code for preceeding string */
X    unsigned char   foll;    /* char following string */
X{
X    unsigned short  local, tempnext;    /* scratch storage */
X    struct entry   *ep;    /* allows faster table handling */
X
X    local = (*h) (pred, foll);    /* get initial hash value */
X
X    if (!string_tab[local].used)    /* if that spot is free */
X        return local;    /* then that's all we need */
X
X    else {            /* else a collision has occured */
X        local = eolist(local);    /* move to last duplicate */
X
X        /*
X         * We must find an empty spot. We start looking 101 places
X         * down the table from the last duplicate.
X         */
X
X        tempnext = (local + 101) & 0x0FFF;
X        ep = &string_tab[tempnext];    /* initialize pointer */
X
X        while (ep->used) {    /* while empty spot not found */
X            if (++tempnext == TABSIZE) {    /* if we are at the end */
X                tempnext = 0;    /* wrap to beginning of table */
X                ep = string_tab;
X            } else
X                ++ep;    /* point to next element in table */
X        }
X
X        /*
X         * local still has the pointer to the last duplicate, while
X         * tempnext has the pointer to the spot we found.  We use
X         * this to maintain the chain of pointers to duplicates.
X         */
X
X        string_tab[local].next = tempnext;
X
X        return tempnext;
X    }
X}
X
X/*
X * The init_tab() routine is used to initialize our hash table. You realize,
X * of course, that "initialize" is a complete misnomer.
X */
X
Xstatic          void
Xinit_tab()
X{                /* set ground state in hash table */
X    unsigned int    i;    /* table index */
X
X    setmem((char *) string_tab, sizeof(string_tab), 0);
X
X    for (i = 0; i < 256; i++)    /* list all single byte strings */
X        upd_tab(NO_PRED, i);
X
X    inbuf = EMPTY;        /* nothing is in our buffer */
X}
X
X/*
X * The upd_tab routine is used to add a new entry to the string table. As
X * previously stated, no checks are made to ensure that the table has any
X * room.  This must be done elsewhere.
X */
X
Xvoid
Xupd_tab(pred, foll)        /* add an entry to the table */
X    unsigned short  pred;    /* code for preceeding string */
X    unsigned short  foll;    /* character which follows string */
X{
X    struct entry   *ep;    /* pointer to current entry */
X
X    /* calculate offset just once */
X
X    ep = &string_tab[hash(pred, foll)];
X
X    ep->used = TRUE;    /* this spot is now in use */
X    ep->next = 0;        /* no duplicates after this yet */
X    ep->predecessor = pred;    /* note code of preceeding string */
X    ep->follower = foll;    /* note char after string */
X}
X
X/*
X * This algorithm encoded a file into twelve bit strings (three nybbles). The
X * gocode() routine is used to read these strings a byte (or two) at a time.
X */
X
Xstatic          int
Xgocode(fd)            /* read in a twelve bit code */
X    FILE           *fd;    /* file to get code from */
X{
X    unsigned short  localbuf, returnval;
X    int             temp;
X
X    if (inbuf == EMPTY) {    /* if on a code boundary */
X        if ((temp = getc_unp(fd)) == EOF)    /* get start of next
X                             * code */
X            return EOF;    /* pass back end of file status */
X        localbuf = temp & 0xFF;    /* mask down to true byte value */
X        if ((temp = getc_unp(fd)) == EOF)
X            /* get end of code, * start of next */
X            return EOF;    /* this should never happen */
X        inbuf = temp & 0xFF;    /* mask down to true byte value */
X
X        returnval = ((localbuf << 4) & 0xFF0) + ((inbuf >> 4) & 0x00F);
X        inbuf &= 0x000F;/* leave partial code pending */
X    } else {        /* buffer contains first nybble */
X        if ((temp = getc_unp(fd)) == EOF)
X            return EOF;
X        localbuf = temp & 0xFF;
X
X        returnval = localbuf + ((inbuf << 8) & 0xF00);
X        inbuf = EMPTY;    /* note no hanging nybbles */
X    }
X    return returnval;    /* pass back assembled code */
X}
X
Xstatic          void
Xpush(c)                /* push char onto stack */
X    int             c;    /* character to push */
X{
X    stack[sp] = ((char) c);    /* coerce integer into a char */
X
X    if (++sp >= TABSIZE)
X        abort("Stack overflow\n");
X}
X
Xstatic          int
Xpop()
X{                /* pop character from stack */
X    if (sp > 0)
X        return ((int) stack[--sp]);    /* leave ptr at next empty
X                         * slot */
X
X    else
X        return EMPTY;
X}
X
X/***** LEMPEL-ZEV DECOMPRESSION *****/
X
Xstatic int      code_count;    /* needed to detect table full */
Xstatic int      firstc;        /* true only on first character */
X
Xvoid
Xinit_ucr(new)            /* get set for uncrunching */
X    int             new;    /* true to use new hash function */
X{
X    if (new)        /* set proper hash function */
X        h = newh;
X    else
X        h = oldh;
X
X    sp = 0;            /* clear out the stack */
X    init_tab();        /* set up atomic code definitions */
X    code_count = TABSIZE - 256;    /* note space left in table */
X    firstc = 1;        /* true only on first code */
X}
X
Xint
Xgetc_ucr(f)            /* get next uncrunched byte */
X    FILE           *f;    /* file containing crunched data */
X{
X    int             code, newcode;
X    static int      oldcode, finchar;
X    struct entry   *ep;    /* allows faster table handling */
X
X    if (firstc) {        /* first code is always known */
X        firstc = FALSE;    /* but next will not be first */
X        oldcode = gocode(f);
X        return finchar = string_tab[oldcode].follower;
X    }
X    if (!sp) {        /* if stack is empty */
X        if ((code = newcode = gocode(f)) == EOF)
X            return EOF;
X
X        ep = &string_tab[code];    /* initialize pointer */
X
X        if (!ep->used) {/* if code isn't known */
X            code = oldcode;
X            ep = &string_tab[code];    /* re-initialize pointer */
X            push(finchar);
X        }
X        while (ep->predecessor != NO_PRED) {
X            push(ep->follower);    /* decode string backwards */
X            code = ep->predecessor;
X            ep = &string_tab[code];
X        }
X
X        push(finchar = ep->follower);    /* save first character also */
X
X        /*
X         * The above loop will terminate, one way or another, with
X         * string_tab[code].follower equal to the first character in
X         * the string.
X         */
X
X        if (code_count) {    /* if room left in string table */
X            upd_tab(oldcode, finchar);
X            --code_count;
X        }
X        oldcode = newcode;
X    }
X    return pop();        /* return saved character */
X}
________This_Is_The_END________
if test `wc -c < arclzw.c` -ne    22109; then
    echo 'shar: arclzw.c was damaged during transit (should have been    22109 bytes)'
fi
fi        ; : end of overwriting check
echo 'x - arcmatch.c'
if test -f arcmatch.c; then echo 'shar: not overwriting arcmatch.c'; else
sed 's/^X//' << '________This_Is_The_END________' > arcmatch.c
X/*
X * $Header: arcmatch.c,v 1.5 88/06/01 19:41:08 hyc Locked $
X */
X
X/*
X * ARC - Archive utility - ARCMATCH
X *
X * Version 2.17, created on 12/17/85 at 20:32:18
X *
X * (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
X *
X * By:  Thom Henderson
X *
X * Description: This file contains service routines needed to maintain an
X * archive.
X *
X * Language: Computer Innovations Optimizing C86
X */
X#include <stdio.h>
X#include "arc.h"
X
Xint    strcmp(), strlen();
Xvoid    abort();
Xchar    *strcpy();
X
Xint
Xmatch(n, t)            /* test name against template */
X    char           *n;    /* name to test */
X    char           *t;    /* template to test against */
X{
X#if    MTS
X    fortran         patbuild(), patmatch(), patfree();
X    static int      patlen = (-1);
X    static int      patwork = 0;
X    static int      patswch = 0;
X    char            patccid[4];
X    static char     patchar[2] = "?";
X    static char     oldtemp[16] = 0;
X    int             namlen, RETCODE;
X
X    if (strcmp(t, oldtemp)) {
X        if (patwork)
X            patfree(&patwork);
X        strcpy(oldtemp, t);
X        patlen = strlen(oldtemp);
X        patbuild(oldtemp, &patlen, &patwork, &patswch, patccid, patchar, _retcode RETCODE);
X        if (RETCODE > 8) {
X            printf("MTS: patbuild returned %d\n", RETCODE);
X            abort("bad wildcard in filename");
X        }
X    }
X    namlen = strlen(n);
X    patmatch(n, &namlen, &patwork, _retcode RETCODE);
X    switch (RETCODE) {
X    case 0:
X        return (1);
X    case 4:
X        return (0);
X    default:
X        abort("wildcard pattern match failed");
X    }
X}
X
X#else
X#if    !UNIX
X    upper(n);
X    upper(t);        /* avoid case problems */
X#endif    /* UNIX */
X#if    GEMDOS
X    return(pnmatch(n, t, 0));
X#else
X    /* first match name part */
X
X    while ((*n && *n != '.') || (*t && *t != '.')) {
X        if (*n != *t && *t != '?') {    /* match fail? */
X            if (*t != '*')    /* wildcard fail? */
X                return 0;    /* then no match */
X            else {    /* else jump over wildcard */
X                while (*n && *n != '.')
X                    n++;
X                while (*t && *t != '.')
X                    t++;
X                break;    /* name part matches wildcard */
X            }
X        } else {    /* match good for this char */
X            n++;    /* advance to next char */
X            t++;
X        }
X    }
X
X    if (*n && *n == '.')
X        n++;        /* skip extension delimiters */
X    if (*t && *t == '.')
X        t++;
X
X    /* now match name part */
X
X    while (*n || *t) {
X        if (*n != *t && *t != '?') {    /* match fail? */
X            if (*t != '*')    /* wildcard fail? */
X                return 0;    /* then no match */
X            else
X                return 1;    /* else good enough */
X        } else {    /* match good for this char */
X            n++;    /* advance to next char */
X            t++;
X        }
X    }
X
X    return 1;        /* match worked */
X#endif    /* GEMDOS */
X}
X#endif
X
Xvoid
Xrempath(nargs, arg)        /* remove paths from filenames */
X    int             nargs;    /* number of names */
X    char           *arg[];    /* pointers to names */
X{
X    char           *i, *rindex();    /* string index, reverse indexer */
X    int             n;    /* index */
X
X    for (n = 0; n < nargs; n++) {    /* for each supplied name */
X        if (!(i = rindex(arg[n], '\\')))    /* search for end of
X                             * path */
X            if (!(i = rindex(arg[n], '/')))
X                i = rindex(arg[n], ':');
X        if (i)        /* if path was found */
X            arg[n] = i + 1;    /* then skip it */
X    }
X}
________This_Is_The_END________
if test `wc -c < arcmatch.c` -ne     3026; then
    echo 'shar: arcmatch.c was damaged during transit (should have been     3026 bytes)'
fi
fi        ; : end of overwriting check
echo 'x - arcmisc.c'
if test -f arcmisc.c; then echo 'shar: not overwriting arcmisc.c'; else
sed 's/^X//' << '________This_Is_The_END________' > arcmisc.c
X/*
X * Miscellaneous routines to get ARC running on non-MSDOS systems...
X * $Header: arcmisc.c,v 1.7 88/06/12 19:23:13 hyc Locked $
X */
X
X#include <stdio.h>
X#include <ctype.h>
X#include "arc.h"
X
X#if    MSDOS
X#include <dir.h>
X#include <stat.h>
X#endif
X
X#if    GEMDOS
X#include <osbind.h>
X#include <stat.h>
Xchar           *index(), *rindex();
X
Xvoid
Xexitpause()
X{
X    while (Cconis())
X        Cnecin();
X    fprintf(stderr, "Press any key to continue: ");
X    fflush(stderr);
X    Cnecin();
X    fprintf(stderr, "\n");
X}
X
Xint
Xchdir(dirname)
X    char           *dirname;
X{
X    char           *i;
X    int             drv;
X
X    i = dirname;
X    if ((i = index(dirname, ':')) != NULL) {
X        drv = i[-1];
X        i++;        /* Move past device spec */
X        if (drv > '\'')
X            drv -= 'a';
X        else
X            drv -= 'A';
X        if (drv >= 0 && drv < 16)
X            Dsetdrv(drv);
X    }
X    if (*i != '\0')
X        return (Dsetpath(i));
X}
X#endif
X
X#if    UNIX
X#include <sys/types.h>
X#include <sys/dir.h>
X#include <sys/stat.h>
X    int    rename();
X#endif
X
X#if    SYSV
X#include <dirent.h>
X#define DIRECT dirent
X#else
X#define DIRECT direct
X#endif
X
Xchar           *strcpy(), *strcat(), *malloc();
Xint             strlen();
X
Xint
Xmove(oldnam, newnam)
X    char           *oldnam, *newnam;
X{
X    FILE           *fopen(), *old, *new;
X    struct stat     oldstat;
X    char           *strcpy();
X    void        filecopy();
X#if    GEMDOS
X    if (Frename(0, oldnam, newnam))
X#else
X    if (rename(oldnam, newnam))
X#endif
X    {
X        if (stat(oldnam, &oldstat))    /* different partition? */
X            return (-1);
X        old = fopen(oldnam, "rb");
X        if (old == NULL)
X            return (-1);
X        new = fopen(newnam, "wb");
X        if (new == NULL)
X            return (-1);
X        filecopy(old, new, oldstat.st_size);
X        unlink(oldnam);
X    }
X    return 0;
X}
X
Xstatic void
X_makefn(source, dest)
X    char           *source;
X    char           *dest;
X{
X    int             j;
X#if    MSDOS
X    char           *setmem();
X#else
X    char           *memset();
X#endif
X
X    setmem(dest, 17, 0);    /* clear result field */
X    for (j = 0; *source && *source != '.'; ++source)
X        if (j < 8)
X            dest[j++] = *source;
X    for (j = 9; *source; ++source)
X        if (j < 13)
X            dest[j++] = *source;
X}
X/*
X * make a file name using a template
X */
X
Xchar           *
Xmakefnam(rawfn, template, result)
X    char           *rawfn;    /* the original file name */
X    char           *template;    /* the template data */
X    char           *result;    /* where to place the result */
X{
X    char            et[17], er[17], rawbuf[STRLEN], *i, *rindex();
X
X    *rawbuf = 0;
X    strcpy(rawbuf, rawfn);
X#if    MTS
X    i = rawbuf;
X    if (rawbuf[0] == tmpchr[0]) {
X        i++;
X        strcpy(rawfn, i);
X    } else
X#endif
X    if ((i = rindex(rawbuf, CUTOFF))) {
X        i++;
X        strcpy(rawfn, i);
X    }
X#if    DOS
X    else if ((i = rindex(rawbuf, ':'))) {
X        i++;
X        strcpy(rawfn, i);
X    }
X#endif
X    if (i)
X        *i = 0;
X    else
X        *rawbuf = 0;
X
X    _makefn(template, et);
X    _makefn(rawfn, er);
X    *result = 0;        /* assure no data */
X    strcat(result, rawbuf);
X    strcat(result, er[0] ? er : et);
X    strcat(result, er[9] ? er + 9 : et + 9);
X    return ((char *) &result[0]);
X}
X
X#if    MSDOS || SYSV
X
Xint
Xalphasort(dirptr1, dirptr2)
X    struct DIRECT **dirptr1, **dirptr2;
X{
X    return (strcmp((*dirptr1)->d_name, (*dirptr2)->d_name));
X}
X
X#endif
X
Xvoid
Xupper(string)
X    char           *string;
X{
X    char           *p;
X
X    for (p = string; *p; p++)
X        if (islower(*p))
X            *p = toupper(*p);
X}
X/* VARARGS1 */
Xvoid
Xabort(s, arg1, arg2, arg3)
X    char           *s;
X{
X    fprintf(stderr, "ARC: ");
X    fprintf(stderr, s, arg1, arg2, arg3);
X    fprintf(stderr, "\n");
X#if    UNIX
X    perror("UNIX");
X#endif
X#if    GEMDOS
X    exitpause();
X#endif
X    exit(1);
X}
X
X#if    !MTS
X
Xchar           *
Xgcdir(dirname)
X    char           *dirname;
X
X{
X    char           *getwd();
X#if    GEMDOS
X    int             drv;
X    char           *buf;
X#endif
X    if (dirname == NULL || strlen(dirname) == 0)
X        dirname = (char *) malloc(1024);
X
X#if    !GEMDOS
X    getwd(dirname);
X#else
X    buf = dirname;
X    *buf++ = (drv = Dgetdrv()) + 'A';
X    *buf++ = ':';
X    Dgetpath(buf, 0);
X#endif
X    return (dirname);
X}
X
X#if    UNIX
Xchar           *pattern;    /* global so that fmatch can use it */
X#endif
X
Xchar           *
Xdir(filename)        /* get files, one by one */
X    char           *filename;    /* template, or NULL */
X{
X#if    GEMDOS
X    static int      Nnum = 0;
X    static DMABUFFER dbuf, *saved;
X    char           *name;
X
X    if (Nnum == 0) {    /* first call */
X        saved = (DMABUFFER *) Fgetdta();
X        Fsetdta(&dbuf);
X        if (Fsfirst(filename, 0) == 0) {
X            name = malloc(FNLEN);
X            strcpy(name, dbuf.d_fname);
X            Nnum++;
X            return (name);
X        } else {
X            Fsetdta(saved);
X            return (NULL);
X        }
X    } else {
X        if (Fsnext() == 0) {
X            name = malloc(FNLEN);
X            strcpy(name, dbuf.d_fname);
X            return (name);
X        } else {
X            Nnum = 0;
X            Fsetdta(saved);
X            return (NULL);
X        }
X    }
X}
X#else
X    static struct DIRECT **namelist;
X    static char   **NameList;
X    static char    namecopy[STRLEN], *dirname;
X#if    UNIX
X    int             alphasort();
X    int             scandir();
X#endif                /* UNIX */
X    int             fmatch();
X    static int      Nnum = 0, ii;
X    char        *rindex();
X
X
X    if (Nnum == 0) {    /* first call */
X        strcpy(namecopy,filename);
X        if(pattern=rindex(namecopy,CUTOFF)) {
X            *pattern = 0;
X            pattern++;
X            dirname = namecopy;
X        } else {
X            pattern = filename;
X            dirname = ".";
X        }
X        Nnum = scandir(dirname, &namelist, fmatch, alphasort);
X        NameList = (char **) malloc(Nnum * sizeof(char *));
X        for (ii = 0; ii < Nnum; ii++) {
X            (NameList)[ii] = malloc(strlen(namelist[ii]->d_name) + 1);
X            strcpy((NameList)[ii], namelist[ii]->d_name);
X        }
X        ii = 0;
X    }
X    if (ii >= Nnum) {    /* all out of files */
X        if (Nnum) {    /* there were some files found */
X            for (ii = 0; ii < Nnum; ii++)
X                free(namelist[ii]);
X            free(namelist);
X        }
X        Nnum = 0;
X        return (NULL);
X    } else {
X        return ((NameList)[ii++]);
X    }
X}
X
X/*
X * Filename match - here, * matches everything
X */
X
Xint
Xfmatch(direntry)
X    struct DIRECT  *direntry;
X{
X    char           *string;
X
X    string = direntry->d_name;
X
X    if (!strcmp(pattern, "") || !strcmp(pattern, "*.*") || !strcmp(pattern, "*"))
X        return (1);
X    return (match(string, pattern));
X}
X#endif                /* GEMDOS */
X#else
X/* dir code for MTS under Bell Labs C... */
X
Xchar           *
Xdir(filepattern)
X    char           *filepattern;    /* template or NULL */
X{
X    char           *malloc(), *index();
X#if    USECATSCAN
X    fortran void    catscan(), fileinfo();
X
X    struct catname {
X        short           len;
X        char            name[257];
X    }               pattern;
X
X    struct catval {
X        int             maxlen;
X        int             actlen;
X        char            name[257];
X    }               catreturn;
X
X    char           *i;
X    int             j, RETCODE;
X
X    static int      catptr = 0;
X    static int      catflag = 0x200;
X    static int      cattype = 1;
X    static int      patflag = 0;
X
X    catreturn.maxlen = 256;
X
X    if (patflag) {
X        patflag = 0;
X        catptr = 0;
X        return (NULL);
X    }
X    if (filepattern) {
X        strcpy(pattern.name, filepattern);
X        pattern.len = strlen(filepattern);
X        if (!index(filepattern, '?'))
X            patflag = 1;
X    }
X    if (patflag) {
X        fileinfo(&pattern, &cattype, "CINAME  ", &catreturn, _retcode RETCODE);
X        catptr = RETCODE ? 0 : 1;
X    } else
X        catscan(&pattern, &catflag, &cattype, &catreturn, &catptr);
X
X    if (!catptr)
X        return (NULL);
X    else {
X        char           *k;
X
X        k = index(catreturn.name, ' ');
X        if (k)
X            *k = 0;
X        else {
X            j = catreturn.actlen;
X            catreturn.name[j] = 0;
X        }
X        k = catreturn.name;
X        if (catreturn.name[0] == tmpchr[0])
X            k++;
X        else if ((k = index(catreturn.name, sepchr[0])))
X            k++;
X        else
X            k = catreturn.name;
X        j = strlen(k);
X        i = malloc(++j);
X        strcpy(i, k);
X        return (i);
X    }
X#else
X    fortran void    gfinfo();
X    static char     gfname[24];
X    static char     pattern[20];
X    static int      gfdummy[2] = {
X                      0, 0
X    },              gfflags;
X    int             i, RETCODE;
X    char           *j, *k;
X
X    if (filepattern) {
X        strcpy(pattern, filepattern);
X        strcat(pattern, " ");
X        for (i = 20; i < 24; i++)
X            gfname[i] = '\0';
X        if (index(pattern, '?'))
X            gfflags = 0x0C;
X        else
X            gfflags = 0x09;
X    } else if (gfflags == 0x09)
X        return (NULL);
X
X    gfinfo(pattern, gfname, &gfflags, gfdummy, gfdummy, gfdummy, _retcode RETCODE);
X    if (RETCODE)
X        return (NULL);
X    else {
X        k = index(gfname, ' ');
X        *k = '\0';
X        k = gfname;
X        if (gfname[0] == tmpchr[0])
X            k++;
X        else if ((k = index(gfname, sepchr[0])))
X            k++;
X        else
X            k = gfname;
X        i = strlen(k);
X        j = malloc(++i);
X        strcpy(j, k);
X        return (j);
X    }
X#endif
X}
X
Xint
Xunlink(path)
X    char           *path;    /* name of file to delete */
X{
X    fortran void    destroy();
X    int             RETCODE;
X
X    char            name[258];
X
X    strcpy(name, path);
X    strcat(name, " ");
X    destroy(name, _retcode RETCODE);
X    if (RETCODE)
X        return (-1);
X    else
X        return (0);
X}
X#endif
________This_Is_The_END________
if test `wc -c < arcmisc.c` -ne     8418; then
    echo 'shar: arcmisc.c was damaged during transit (should have been     8418 bytes)'
fi
fi        ; : end of overwriting check
echo 'x - arcpack.c'
if test -f arcpack.c; then echo 'shar: not overwriting arcpack.c'; else
sed 's/^X//' << '________This_Is_The_END________' > arcpack.c
X/*
X * $Header: arcpack.c,v 1.9 88/06/02 16:27:36 hyc Locked $
X */
X
X/*  ARC - Archive utility - ARCPACK
X
X    Version 3.49, created on 04/21/87 at 11:26:51
X
X(C) COPYRIGHT 1985-87 by System Enhancement Associates; ALL RIGHTS RESERVED
X
X    By:     Thom Henderson
X
X    Description:
X     This file contains the routines used to compress a file
X     when placing it in an archive.
X
X    Language:
X     Computer Innovations Optimizing C86
X*/
X#include <stdio.h>
X#include "arc.h"
X#if    MTS
X#include <ctype.h>
X#endif
X
Xvoid    setcode(), sqinit_cm(), sqputc_cm(), init_cm(), putc_cm();
Xvoid    filecopy(), abort(), putc_tst();
Xint    getch(), addcrc();
X
X/* stuff for non-repeat packing */
X
X#define DLE 0x90        /* repeat sequence marker */
X
Xstatic unsigned char state;    /* current packing state */
X
X/* non-repeat packing states */
X
X#define NOHIST  0        /* don't consider previous input */
X#define SENTCHAR 1        /* lastchar set, no lookahead yet */
X#define SENDNEWC 2        /* run over, send new char next */
X#define SENDCNT 3        /* newchar set, send count next */
X
X/* packing results */
X
Xstatic long     stdlen;        /* length for standard packing */
Xstatic short    crcval;        /* CRC check value */
X
Xvoid
Xpack(f, t, hdr)            /* pack file into an archive */
X    FILE           *f, *t;    /* source, destination */
X    struct heads   *hdr;    /* pointer to header data */
X{
X    int             c;    /* one character of stream */
X    long            ncrlen;    /* length after packing */
X    long        huflen;    /* length after squeezing */
X    long            lzwlen;    /* length after crunching */
X    long        pred_sq(), file_sq();    /* stuff for squeezing */
X    long            pred_cm(), sqpred_cm();    /* dynamic crunching cleanup */
X    long            tloc, ftell();    /* start of output */
X    int        getch();
X    int             getc_ncr();
X    void            putc_pak();
X
X    /* first pass - see which method is best */
X
X    tloc = ftell(t);    /* note start of output */
X
X    if (!nocomp) {        /* if storage kludge not active */
X        if (note) {
X            printf(" analyzing, ");
X            fflush(stdout);
X        }
X        state = NOHIST;    /* initialize ncr packing */
X        stdlen = ncrlen = 0;    /* reset size counters */
X        crcval = 0;    /* initialize CRC check value */
X        setcode();    /* initialize encryption */
X        init_sq();    /* initialize for squeeze scan */
X
X        if (dosquash) {
X            sqinit_cm();
X            while ((c = getch(f)) != EOF) {    /* for each byte of file */
X                ncrlen++;    /* one more packed byte */
X                scan_sq(c);    /* see what squeezing can do */
X                sqputc_cm(c, t);    /* see what squashing
X                             * can do */
X            }
X            lzwlen = sqpred_cm(t);
X        } else {
X            init_cm(t);    /* initialize for crunching */
X
X            while ((c = getc_ncr(f)) != EOF) {    /* for each byte of file */
X                ncrlen++;    /* one more packed byte */
X                scan_sq(c);    /* see what squeezing can do */
X                putc_cm(c, t);    /* see what crunching can do */
X            }
X            lzwlen = pred_cm(t);    /* finish up after crunching */
X        }
X        huflen = pred_sq();    /* finish up after squeezing */
X    } else {        /* else kludge the method */
X        stdlen = 0;    /* make standard look best */
X        ncrlen = huflen = lzwlen = 1;
X    }
X
X    /* standard set-ups common to all methods */
X
X    fseek(f, 0L, 0);    /* rewind input */
X    hdr->crc = crcval;    /* note CRC check value */
X    hdr->length = stdlen;    /* set actual file length */
X    state = NOHIST;        /* reinitialize ncr packing */
X    setcode();        /* reinitialize encryption */
X
X    /* choose and use the shortest method */
X
X    if (kludge && note)
X        printf("\n\tS:%ld  P:%ld  S:%ld  C:%ld,\t ",
X            stdlen, ncrlen, huflen, lzwlen);
X
X    if (stdlen <= ncrlen && stdlen <= huflen && stdlen <= lzwlen) {
X        if (note) {
X            printf("storing, ");    /* store without compression */
X            fflush(stdout);
X        }
X        hdrver = 2;    /* note packing method */
X        fseek(t, tloc, 0);    /* reset output for new method */
X        stdlen = crcval = 0;    /* recalc these for kludge */
X        while ((c = getch(f)) != EOF)    /* store it straight */
X            putc_pak(c, t);
X        hdr->crc = crcval;
X        hdr->length = hdr->size = stdlen;
X    } else if (ncrlen < lzwlen && ncrlen < huflen) {
X        if (note) {
X            printf("packing, ");    /* pack with repeat
X            fflush(stdout);         * suppression */
X        }
X        hdrver = 3;    /* note packing method */
X        hdr->size = ncrlen;    /* set data length */
X        fseek(t, tloc, 0);    /* reset output for new method */
X        while ((c = getc_ncr(f)) != EOF)
X            putc_pak(c, t);
X    } else if (huflen < lzwlen) {
X        if (note) {
X            printf("squeezing, ");
X            fflush(stdout);
X        }
X        hdrver = 4;    /* note packing method */
X        fseek(t, tloc, 0);    /* reset output for new method */
X        hdr->size = file_sq(f, t);    /* note final size */
X    } else {
X        if (note)
X            printf(dosquash ? "squashed, " : "crunched, ");
X        hdrver = dosquash ? 9 : 8;
X        hdr->size = lzwlen;    /* size should not change */
X    }
X
X    /* standard cleanups common to all methods */
X
X    if (note)
X        printf("done. (%ld%%)\n",100L - (100L*hdr->size)/hdr->length);
X}
X
X/*
X * Non-repeat compression - text is passed through normally, except that a
X * run of more than two is encoded as:
X *
X * <char> <DLE> <count>
X *
X * Special case: a count of zero indicates that the DLE is really a DLE, not a
X * repeat marker.
X */
X
Xint
Xgetc_ncr(f)            /* get bytes with collapsed runs */
X    FILE           *f;    /* file to get from */
X{
X    static int      lastc;    /* value returned on last call */
X    static int      repcnt;    /* repetition counter */
X    static int      c;    /* latest value seen */
X
X    switch (state) {    /* depends on our state */
X    case NOHIST:        /* no relevant history */
X        state = SENTCHAR;
X        return lastc = getch(f);    /* remember the value next
X                         * time */
X
X    case SENTCHAR:        /* char was sent. look ahead */
X        switch (lastc) {/* action depends on char */
X        case DLE:    /* if we sent a real DLE */
X            state = NOHIST;    /* then start over again */
X            return 0;    /* but note that the DLE was real */
X
X        case EOF:    /* EOF is always a special case */
X            return EOF;
X
X        default:    /* else test for a repeat */
X            for (repcnt = 1; (c = getch(f)) == lastc && repcnt < 255; repcnt++);
X            /* find end of run */
X
X            switch (repcnt) {    /* action depends on run size */
X            case 1:/* not a repeat */
X                return lastc = c;    /* but remember value
X                             * next time */
X
X            case 2:/* a repeat, but too short */
X                state = SENDNEWC;    /* send the second one
X                             * next time */
X                return lastc;
X
X            default:    /* a run - compress it */
X                state = SENDCNT;    /* send repeat count
X                             * next time */
X                return DLE;    /* send repeat marker this
X                         * time */
X            }
X        }
X
X    case SENDNEWC:        /* send second char of short run */
X        state = SENTCHAR;
X        return lastc = c;
X
X    case SENDCNT:        /* sent DLE, now send count */
X        state = SENDNEWC;
X        return repcnt;
X
X    default:
X        abort("Bug - bad ncr state\n");
X    }
X}
X
Xint
Xgetch(f)            /* special get char for packing */
X    FILE           *f;    /* file to get from */
X{
X    int        c;    /* a char from the file */
X#if    !DOS
X    static int      cr = 0;    /* add \r before \n ? */
X
X    if (cr) {
X        c = '\n';
X#if    MTS
X        c = toascii(c);
X#endif
X        crcval = addcrc(crcval, c);
X        stdlen++;
X        cr = 0;
X        return (c);
X    }
X#endif
X
X    if ((c = fgetc(f)) != EOF) {    /* if not the end of file */
X#if    !DOS
X        if (!image && (c == '\n')) {
X            c = '\r';
X            cr = 1;
X        }
X#endif
X#if    MTS
X        if (!image)
X            c = toascii(c);
X#endif
X        crcval = addcrc(crcval, c);    /* then update CRC check
X                         * value */
X        stdlen++;    /* and bump length counter */
X    }
X    return c;
X}
X
Xvoid
Xputc_pak(c, f)            /* put a packed byte into archive */
X    char            c;    /* byte to put */
X    FILE           *f;    /* archive to put it in */
X{
X    unsigned char        code();
X    putc_tst(code(c), f);    /* put encoded byte, with checks */
X}
________This_Is_The_END________
if test `wc -c < arcpack.c` -ne     7376; then
    echo 'shar: arcpack.c was damaged during transit (should have been     7376 bytes)'
fi
fi        ; : end of overwriting check
echo 'x - arcrun.c'
if test -f arcrun.c; then echo 'shar: not overwriting arcrun.c'; else
sed 's/^X//' << '________This_Is_The_END________' > arcrun.c
X/*
X * $Header: arcrun.c,v 1.3 88/06/01 19:57:16 hyc Locked $
X */
X
X/*
X * ARC - Archive utility - ARCRUN
X *
X * Version 1.20, created on 03/24/86 at 19:34:31
X *
X * (C) COPYRIGHT 1985,85 by System Enhancement Associates; ALL RIGHTS RESERVED
X *
X * By:  Thom Henderson
X *
X * Description: This file contains the routines used to "run" a file which is
X * stored in an archive.  At present, all we really do is (a) extract a
X * temporary file, (b) give its name as a system command, and then (c) delete
X * the file.
X *
X * Language: Computer Innovations Optimizing C86
X */
X#include <stdio.h>
X#include "arc.h"
X
Xvoid    rempath(), openarc(), closearc(), abort();
Xchar    *strcat();
X
Xvoid
Xrunarc(num, arg)        /* run file from archive */
X    int             num;    /* number of arguments */
X    char           *arg[];    /* pointers to arguments */
X{
X    struct heads    hdr;    /* file header */
X    char           *makefnam();    /* filename fixer */
X    char            buf[STRLEN];    /* filename buffer */
X    FILE           *fopen();/* file opener */
X    int             runfile();
X    char           *dummy[2];
X
X    dummy[0]="dummy";
X    dummy[1]=NULL;
X    rempath(num, arg);    /* strip off paths */
X
X    openarc(0);        /* open archive for reading */
X
X    if (num) {        /* if files were named */
X        while (readhdr(&hdr, arc)) {    /* while more files to check */
X            if (match(hdr.name, makefnam(arg[0], ".*", buf)))
X                runfile(&hdr, num, arg);
X            else
X                fseek(arc, hdr.size, 1);
X        }
X    } else
X        while (readhdr(&hdr, arc))    /* else run all files */
X            runfile(&hdr, 1, dummy);
X
X    closearc(0);        /* close archive after changes */
X}
X
Xstatic          int
Xrunfile(hdr, num, arg)        /* run a file */
X    struct heads   *hdr;    /* pointer to header data */
X    int             num;    /* number of arguments */
X    char           *arg[];    /* pointers to arguments */
X{
X    FILE           *tmp, *fopen();    /* temporary file */
X    char           *dir, *gcdir();    /* directory stuff */
X    char            buf[STRLEN], *makefnam();    /* temp file name, fixer */
X#if    DOS
X    char        nbuf[64], *i, *rindex();
X#endif
X#if    !GEMDOS
X    int             n;    /* index */
X    char            sys[STRLEN];    /* invocation command buffer */
X#endif
X
X    /* makefnam("$ARCTEMP",hdr->name,buf); */
X#if    UNIX
X    sprintf(buf, "%s.RUN", arctemp);
X    strcpy(sys, buf);
X#else
X    strcpy(nbuf, arctemp);
X    makefnam(nbuf,hdr->name,buf);
X    i = rindex(buf,'.');
X#endif
X#if    MSDOS
X    if (!strcmp(i, ".BAS")) {
X        strcpy(sys, "BASICA ");
X        strcat(sys, buf);
X    }
X    else if (!strcmp(i, ".BAT")
X         || !strcmp(i, ".COM")
X         || !strcmp(i, ".EXE"))
X        strcpy(sys, buf);
X
X    else {
X        if (warn) {
X            printf("File %s is not a .BAS, .BAT, .COM, or .EXE\n",
X                   hdr->name);
X            nerrs++;
X        }
X        fseek(arc, hdr->size, 1);    /* skip this file */
X        return;
X    }
X#endif
X#if    GEMDOS
X      if (strcmp(i, ".PRG")
X              && strcmp(i, ".TTP")
X              && strcmp(i, ".TOS"))
X      {
X              if (warn) {
X                      printf("File %s is not a .PRG, .TOS, or .TTP\n",
X                              hdr->name);
X                      nerrs++;
X              }
X              fseek(arc, hdr->size, 1);       /* skip this file */
X              return;
X      }
X#endif
X
X    if (warn)
X        if (tmp = fopen(buf, "r"))
X            abort("Temporary file %s already exists", buf);
X    if (!(tmp = fopen(buf, "wb")))
X        abort("Unable to create temporary file %s", buf);
X
X    if (note)
X        printf("Invoking file: %s\n", hdr->name);
X
X    dir = gcdir("");    /* see where we are */
X    unpack(arc, tmp, hdr);    /* unpack the entry */
X    fclose(tmp);        /* release the file */
X    chmod(buf, "700");    /* make it executable */
X#if    GEMDOS
X    execve(buf, arg, NULL);
X#else
X    for (n = 1; n < num; n++) {    /* add command line arguments */
X        strcat(sys, " ");
X        strcat(sys, arg[n]);
X    }
X    system(buf);        /* try to invoke it */
X#endif
X    chdir(dir);
X    free(dir);        /* return to whence we started */
X    if (unlink(buf) && warn) {
X        printf("Cannot unsave temporary file %s\n", buf);
X        nerrs++;
X    }
X}
________This_Is_The_END________
if test `wc -c < arcrun.c` -ne     3838; then
    echo 'shar: arcrun.c was damaged during transit (should have been     3838 bytes)'
fi
fi        ; : end of overwriting check
echo 'x - arcs.h'
if test -f arcs.h; then echo 'shar: not overwriting arcs.h'; else
sed 's/^X//' << '________This_Is_The_END________' > arcs.h
X/*
X * $Header: arcs.h,v 1.2 88/04/17 18:53:19 hyc Exp $
X */
X
X/*
X * ARC - Archive utility - Archive file header format
X *
X * Version 2.12, created on 12/17/85 at 14:40:26
X *
X * (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
X *
X * By:  Thom Henderson
X *
X * Description: This file defines the format of an archive file header,
X * excluding the archive marker and the header version number.
X *
X * Each entry in an archive begins with a one byte archive marker, which is set
X * to 26.  The marker is followed by a one byte header type code, from zero
X * to 7.
X *
X * If the header type code is zero, then it is an end marker, and no more data
X * should be read from the archive.
X *
X * If the header type code is in the range 2 to 7, then it is followed by a
X * standard archive header, which is defined below.
X *
X * If the header type code is one, then it is followed by an older format
X * archive header.  The older format header does not contain the true length.
X * A header should be read for a length of sizeof(struct heads)-sizeof(long).
X * Then set length equal to size and change the header version to 2.
X *
X * Programming note: The crc value given in the header is based on the unpacked
X * data.
X *
X * Language: Computer Innovations Optimizing C86
X */
X
Xstruct heads {            /* archive entry header format */
X    char    name[FNLEN];        /* file name */
X            long size;        /* size of file, in bytes */
X    unsigned    short date;    /* creation date */
X    unsigned    short time;    /* creation time */
X                short crc;    /* cyclic redundancy check */
X                long length;    /* true file length */
X};
________This_Is_The_END________
if test `wc -c < arcs.h` -ne     1645; then
    echo 'shar: arcs.h was damaged during transit (should have been     1645 bytes)'
fi
fi        ; : end of overwriting check
echo 'x - arcsq.c'
if test -f arcsq.c; then echo 'shar: not overwriting arcsq.c'; else
sed 's/^X//' << '________This_Is_The_END________' > arcsq.c
X/*
X * $Header: arcsq.c,v 1.2 88/06/02 16:27:38 hyc Locked $
X */
X
X/*
X * ARC - Archive utility - ARCSQ
X *
X * Version 3.10, created on 01/30/86 at 20:10:46
X *
X * (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
X *
X * By:  Thom Henderson
X *
X * Description: This file contains the routines used to squeeze a file when
X * placing it in an archive.
X *
X * Language: Computer Innovations Optimizing C86
X *
X * Programming notes: Most of the routines used for the Huffman squeezing
X * algorithm were lifted from the SQ program by Dick Greenlaw, as adapted to
X * CI-C86 by Robert J. Beilstein.
X */
X#include <stdio.h>
X#include "arc.h"
X
X/* stuff for Huffman squeezing */
X
X#define TRUE 1
X#define FALSE 0
X#define ERROR (-1)
X#define SPEOF 256        /* special endfile token */
X#define NOCHILD (-1)        /* marks end of path through tree */
X#define NUMVALS 257        /* 256 data values plus SPEOF */
X#define NUMNODES (NUMVALS+NUMVALS-1)    /* number of nodes */
X#define MAXCOUNT (unsigned short) 65535    /* biggest unsigned integer */
X
X/*
X * The following array of structures are the nodes of the binary trees. The
X * first NUMVALS nodes become the leaves of the final tree and represent the
X * values of the data bytes being encoded and the special endfile, SPEOF. The
X * remaining nodes become the internal nodes of the final tree.
X */
X
Xstruct nd {            /* shared by unsqueezer */
X    unsigned short    weight;    /* number of appearances */
X    short        tdepth;    /* length on longest path in tree */
X    short        lchild, rchild;    /* indices to next level */
X}               node[NUMNODES];    /* use large buffer */
X
Xstatic int      dctreehd;    /* index to head of final tree */
X
X/*
X * This is the encoding table: The bit strings have first bit in low bit.
X * Note that counts were scaled so code fits unsigned integer.
X */
X
Xstatic int      codelen[NUMVALS];    /* number of bits in code */
Xstatic unsigned short code[NUMVALS];    /* code itself, right adjusted */
Xstatic unsigned short tcode;    /* temporary code value */
Xstatic long     valcount[NUMVALS];    /* actual count of times seen */
X
X/* Variables used by encoding process */
X
Xstatic int      curin;        /* value currently being encoded */
Xstatic int      cbitsrem;    /* # of code string bits left */
Xstatic unsigned short ccode;    /* current code right justified */
X
Xint
Xinit_sq()
X{                /* prepare for scanning pass */
X    int             i;    /* node index */
X
X    /*
X     * Initialize all nodes to single element binary trees with zero
X     * weight and depth.
X     */
X
X    for (i = 0; i < NUMNODES; ++i) {
X        node[i].weight = 0;
X        node[i].tdepth = 0;
X        node[i].lchild = NOCHILD;
X        node[i].rchild = NOCHILD;
X    }
X
X    for (i = 0; i < NUMVALS; i++)
X        valcount[i] = 0;
X}
X
Xint
Xscan_sq(c)            /* add a byte to the tables */
X    int             c;    /* byte to add */
X{
X    unsigned short *wp;    /* speeds up weight counting */
X
X    /* Build frequency info in tree */
X
X    if (c == EOF)        /* it's traditional */
X        c = SPEOF;    /* dumb, but traditional */
X
X    if (*(wp = &node[c].weight) != MAXCOUNT)
X        ++(*wp);    /* bump weight counter */
X
X    valcount[c]++;        /* bump byte counter */
X}
X
Xlong
Xpred_sq()
X{                /* predict size of squeezed file */
X    int             i;
X    int             btlist[NUMVALS];    /* list of intermediate
X                         * b-trees */
X    int             listlen;/* length of btlist */
X    unsigned short    ceiling;/* limit for scaling */
X    long            size = 0;    /* predicted size */
X    int             numnodes;    /* # of nodes in simplified tree */
X    int             scale();
X    int             heap();
X    int             bld_tree();
X    int             buildenc();
X    int             init_enc();
X
X    scan_sq(EOF);        /* signal end of input */
X
X    ceiling = MAXCOUNT;
X
X    /* Keep trying to scale and encode */
X
X    do {
X        scale(ceiling);
X        ceiling /= 2;    /* in case we rescale */
X
X        /*
X         * Build list of single node binary trees having leaves for
X         * the input values with non-zero counts
X         */
X
X        for (i = listlen = 0; i < NUMVALS; ++i) {
X            if (node[i].weight != 0) {
X                node[i].tdepth = 0;
X                btlist[listlen++] = i;
X            }
X        }
X
X        /*
X         * Arrange list of trees into a heap with the entry indexing
X         * the node with the least weight at the top.
X         */
X
X        heap(btlist, listlen);
X
X        /* Convert the list of trees to a single decoding tree */
X
X        bld_tree(btlist, listlen);
X
X        /* Initialize the encoding table */
X
X        init_enc();
X
X        /*
X         * Try to build encoding table. Fail if any code is > 16 bits
X         * long.
X         */
X    } while (buildenc(0, dctreehd) == ERROR);
X
X    /* Initialize encoding variables */
X
X    cbitsrem = 0;        /* force initial read */
X    curin = 0;        /* anything but endfile */
X
X    for (i = 0; i < NUMVALS; i++)    /* add bits for each code */
X        size += valcount[i] * codelen[i];
X
X    size = (size + 7) / 8;    /* reduce to number of bytes */
X
X    numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS - 1);
X
X    size += sizeof(short) + 2 * numnodes * sizeof(short);
X
X    return size;
X}
X
X/*
X * The count of number of occurrances of each input value have already been
X * prevented from exceeding MAXCOUNT. Now we must scale them so that their
X * sum doesn't exceed ceiling and yet no non-zero count can become zero. This
X * scaling prevents errors in the weights of the interior nodes of the
X * Huffman tree and also ensures that the codes will fit in an unsigned
X * integer. Rescaling is used if necessary to limit the code length.
X */
X
Xstatic int
Xscale(ceil)
X    unsigned short    ceil;    /* upper limit on total weight */
X{
X    register int    i;
X    int             ovflw, divisor;
X    unsigned short    w, sum;
X    unsigned char   increased;    /* flag */
X
X    do {
X        for (i = sum = ovflw = 0; i < NUMVALS; ++i) {
X            if (node[i].weight > (ceil - sum))
X                ++ovflw;
X            sum += node[i].weight;
X        }
X
X        divisor = ovflw + 1;
X
X        /* Ensure no non-zero values are lost */
X
X        increased = FALSE;
X        for (i = 0; i < NUMVALS; ++i) {
X            w = node[i].weight;
X            if (w < divisor && w != 0) {    /* Don't fail to provide
X                             * a code if it's used
X                             * at all */
X
X                node[i].weight = divisor;
X                increased = TRUE;
X            }
X        }
X    } while (increased);
X
X    /* Scaling factor chosen, now scale */
X
X    if (divisor > 1)
X        for (i = 0; i < NUMVALS; ++i)
X            node[i].weight /= divisor;
X}
X
X/*
X * heap() and adjust() maintain a list of binary trees as a heap with the top
X * indexing the binary tree on the list which has the least weight or, in
X * case of equal weights, least depth in its longest path. The depth part is
X * not strictly necessary, but tends to avoid long codes which might provoke
X * rescaling.
X */
X
Xstatic int
Xheap(list, length)
X    int             list[], length;
X{
X    register int    i;
X    int             adjust();
X
X    for (i = (length - 2) / 2; i >= 0; --i)
X        adjust(list, i, length - 1);
X}
X
X/* Make a heap from a heap with a new top */
X
Xstatic int
Xadjust(list, top, bottom)
X    int             list[], top, bottom;
X{
X    register int    k, temp;
X    int             cmptrees();
X
X    k = 2 * top + 1;    /* left child of top */
X    temp = list[top];    /* remember root node of top tree */
X
X    if (k <= bottom) {
X        if (k < bottom && cmptrees(list[k], list[k + 1]))
X            ++k;
X
X        /* k indexes "smaller" child (in heap of trees) of top */
X        /* now make top index "smaller" of old top and smallest child */
X
X        if (cmptrees(temp, list[k])) {
X            list[top] = list[k];
X            list[k] = temp;
X
X            /* Make the changed list a heap */
X
X            adjust(list, k, bottom);    /* recursive */
X        }
X    }
X}
X
X/*
X * Compare two trees, if a > b return true, else return false. Note
X * comparison rules in previous comments.
X */
X
Xstatic int
Xcmptrees(a, b)
X    int             a, b;    /* root nodes of trees */
X{
X    if (node[a].weight > node[b].weight)
X        return TRUE;
X    if (node[a].weight == node[b].weight)
X        if (node[a].tdepth > node[b].tdepth)
X            return TRUE;
X    return FALSE;
X}
X
X/*
X * HUFFMAN ALGORITHM: develops the single element trees into a single binary
X * tree by forming subtrees rooted in interior nodes having weights equal to
X * the sum of weights of all their descendents and having depth counts
X * indicating the depth of their longest paths.
X *
X * When all trees have been formed into a single tree satisfying the heap
X * property (on weight, with depth as a tie breaker) then the binary code
X * assigned to a leaf (value to be encoded) is then the series of left (0)
X * and right (1) paths leading from the root to the leaf. Note that trees are
X * removed from the heaped list by moving the last element over the top
X * element and reheaping the shorter list.
X */
X
Xstatic int
Xbld_tree(list, len)
X    int             list[];
Xint             len;
X{
X    register int    freenode;    /* next free node in tree */
X    register struct nd *frnp;    /* free node pointer */
X    int             lch, rch;    /* temps for left, right children */
X    int             maxchar();
X
X    /*
X     * Initialize index to next available (non-leaf) node. Lower numbered
X     * nodes correspond to leaves (data values).
X     */
X
X    freenode = NUMVALS;
X
X    while (len > 1) {    /* Take from list two btrees with least
X                 * weight and build an interior node pointing
X                 * to them. This forms a new tree. */
X
X        lch = list[0];    /* This one will be left child */
X
X        /* delete top (least) tree from the list of trees */
X
X        list[0] = list[--len];
X        adjust(list, 0, len - 1);
X
X        /* Take new top (least) tree. Reuse list slot later */
X
X        rch = list[0];    /* This one will be right child */
X
X        /*
X         * Form new tree from the two least trees using a free node
X         * as root. Put the new tree in the list.
X         */
X
X        frnp = &node[freenode];    /* address of next free node */
X        list[0] = freenode++;    /* put at top for now */
X        frnp->lchild = lch;
X        frnp->rchild = rch;
X        frnp->weight = node[lch].weight + node[rch].weight;
X        frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
X
X        /* reheap list  to get least tree at top */
X
X        adjust(list, 0, len - 1);
X    }
X    dctreehd = list[0];    /* head of final tree */
X}
X
Xstatic int
Xmaxchar(a, b)
X{
X    return a > b ? a : b;
X}
X
Xstatic int
Xinit_enc()
X{
X    register int    i;
X
X    /* Initialize encoding table */
X
X    for (i = 0; i < NUMVALS; ++i)
X        codelen[i] = 0;
X}
X
X/*
X * Recursive routine to walk the indicated subtree and level and maintain the
X * current path code in bstree. When a leaf is found the entire code string
X * and length are put into the encoding table entry for the leaf's data value
X * .
X *
X * Returns ERROR if codes are too long.
X */
X
Xstatic int
Xbuildenc(level, root)
X    int             level;    /* level of tree being examined, from zero */
X    int             root;    /* root of subtree is also data value if leaf */
X{
X    register int    l, r;
X
X    l = node[root].lchild;
X    r = node[root].rchild;
X
X    if (l == NOCHILD && r == NOCHILD) {    /* Leaf. Previous path
X                         * determines bit string code
X                         * of length level (bits 0 to
X                         * level - 1). Ensures unused
X                         * code bits are zero. */
X
X        codelen[root] = level;
X        code[root] = tcode & (((unsigned short    ) ~0) >> (16 - level));
X        return (level > 16) ? ERROR : 0;
X    } else {
X        if (l != NOCHILD) {    /* Clear path bit and continue deeper */
X
X            tcode &= ~(1 << level);
X            if (buildenc(level + 1, l) == ERROR)
X                return ERROR;    /* pass back bad statuses */
X        }
X        if (r != NOCHILD) {    /* Set path bit and continue deeper */
X
X            tcode |= 1 << level;
X            if (buildenc(level + 1, r) == ERROR)
X                return ERROR;    /* pass back bad statuses */
X        }
X    }
X    return NULL;        /* it worked if we reach here */
X}
X
Xstatic int
Xput_int(n, f)            /* output an integer */
X    short        n;    /* integer to output */
X    FILE           *f;    /* file to put it to */
X{
X    putc_pak(n & 0xff, f);    /* first the low byte */
X    putc_pak(n >> 8, f);    /* then the high byte */
X}
X
X/* Write out the header of the compressed file */
X
Xstatic long
Xwrt_head(ob)
X    FILE           *ob;
X{
X    register int    l, r;
X    int             i, k;
X    int             numnodes;    /* # of nodes in simplified tree */
X
X    /*
X     * Write out a simplified decoding tree. Only the interior nodes are
X     * written. When a child is a leaf index (representing a data value)
X     * it is recoded as -(index + 1) to distinguish it from interior
X     * indexes which are recoded as positive indexes in the new tree.
X     *
X     * Note that this tree will be empty for an empty file.
X     */
X
X    numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS - 1);
X    put_int(numnodes, ob);
X
X    for (k = 0, i = dctreehd; k < numnodes; ++k, --i) {
X        l = node[i].lchild;
X        r = node[i].rchild;
X        l = l < NUMVALS ? -(l + 1) : dctreehd - l;
X        r = r < NUMVALS ? -(r + 1) : dctreehd - r;
X        put_int(l, ob);
X        put_int(r, ob);
X    }
X
X    return sizeof(short) + numnodes * 2 * sizeof(short);
X}
X
X/*
X * Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
X *
X * There are two unsynchronized bit-byte relationships here. The input stream
X * bytes are converted to bit strings of various lengths via the static
X * variables named c... These bit strings are concatenated without padding to
X * become the stream of encoded result bytes, which this function returns one
X * at a time. The EOF (end of file) is converted to SPEOF for convenience and
X * encoded like any other input value. True EOF is returned after that.
X */
X
Xstatic int
Xgethuff(ib)            /* Returns bytes except for EOF */
X    FILE           *ib;
X{
X    int             rbyte;    /* Result byte value */
X    int             need;    /* number of bits */
X
X    rbyte = 0;
X    need = 8;        /* build one byte per call */
X
X    /*
X     * Loop to build a byte of encoded data. Initialization forces read
X     * the first time.
X     */
X
Xloop:
X    if (cbitsrem >= need) {    /* if current code is big enough */
X        if (need == 0)
X            return rbyte;
X
X        rbyte |= ccode << (8 - need);    /* take what we need */
X        ccode >>= need;    /* and leave the rest */
X        cbitsrem -= need;
X        return rbyte & 0xff;
X    }
X    /* We need more than current code */
X
X    if (cbitsrem > 0) {
X        rbyte |= ccode << (8 - need);    /* take what there is */
X        need -= cbitsrem;
X    }
X    /* No more bits in current code string */
X
X    if (curin == SPEOF) {    /* The end of file token has been encoded. If
X                 * result byte has data return it and do EOF
X                 * next time. */
X
X        cbitsrem = 0;
X        return (need == 8) ? EOF : rbyte + 0;
X    }
X    /* Get an input byte */
X
X    if ((curin = getc_ncr(ib)) == EOF)
X        curin = SPEOF;    /* convenient for encoding */
X
X    ccode = code[curin];    /* get the new byte's code */
X    cbitsrem = codelen[curin];
X
X    goto loop;
X}
X
X/*
X * This routine is used to perform the actual squeeze operation.  It can only
X * be called after the file has been scanned.  It returns the true length of
X * the squeezed entry.
X */
X
Xlong
Xfile_sq(f, t)            /* squeeze a file into an archive */
X    FILE           *f;    /* file to squeeze */
X    FILE           *t;    /* archive to receive file */
X{
X    int             c;    /* one byte of squeezed data */
X    long            size;    /* size after squeezing */
X
X    size = wrt_head(t);    /* write out the decode tree */
X
X    while ((c = gethuff(f)) != EOF) {
X        putc_pak(c, t);
X        size++;
X    }
X
X    return size;        /* report true size */
X}
________This_Is_The_END________
if test `wc -c < arcsq.c` -ne    14613; then
    echo 'shar: arcsq.c was damaged during transit (should have been    14613 bytes)'
fi
fi        ; : end of overwriting check
exit 0

--
Please send comp.sources.unix-related mail to [e-mail].